#include <iostream>
#include <string>
#include <vector>
#include <unordered_set>
using namespace std;

unordered_set<string> myset;
string track;
bool v[10];

void backtrack(string& s, int pos, string& track){
    if(pos == s.length()) {
        myset.insert(track);
        return;
    }
    for(int i=0;i<s.length();i++){
        if(v[i]) continue;
        v[i] = 1;
        track += s[i];
        backtrack(s, pos+1, track);
        v[i] = 0;
        track = track.substr(0,track.length() - 1);
    }
}

vector<string> permutation(string S) {

    backtrack(S, 0, track);

    vector<string> ans;
    for(auto it = myset.begin();it!=myset.end();it++){
        ans.push_back(*it);
    }
    return ans;
}